//package _interview100;
//
//import java.util.Deque;
//import java.util.LinkedList;
//
///**
// * 32. 最长有效括号
// */
//public class No32 {
//    private String s;
//    private int[][] cache;
//
//    /**
//     * 1. 递归（会超出内存）
//     */
//    public int longestValidParentheses1(String s) {
//        int n = s.length();
//        this.s = s;
//        cache = new int[n][n];
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                cache[i][j] = -1;
//            }
//        }
//
//        return dfs(0, n - 1);
//    }
//
//    private int dfs(int i, int j) {
//        if (i >= j) return 0;
//        else if (cache[i][j] != -1) return cache[i][j];
//        else if (valid(i, j)) return cache[i][j] = j - i + 1;
//        else return cache[i][j] = Math.max(dfs(i + 1, j), dfs(i, j - 1));
//    }
//
//    private boolean valid(int left, int right) {
//        Deque<Character> stack = new LinkedList<>();
//
//        for (int i = left; i <= right; i++) {
//            if (s.charAt(i) == '(') stack.push(s.charAt(i));
//            else if (stack.isEmpty()) return false;
//            else stack.pop();
//        }
//        return stack.isEmpty();
//    }
//}
